1. Field of the Invention
The present invention relates generally to node position determination in a network, and more particularly, to systems, methods, and software for determining location of sensors in wireless sensor networks.
2. Related Art
Ad hoc wireless sensor networks involve hundreds or thousands of small, inexpensive devices (sensors) that can communicate with neighboring devices within a limited radio range. The devices include a sensing ability, computational ability, and bi-directional wireless communications ability, and may sometimes include a power supply. By relaying information to each other, they can transmit signals to a command post anywhere within the network.
Wireless sensing devices are used to detect any of a variety of parameters, including without limitation environmental (e.g., pressure, humidity, light, temperature, etc.), motion or force (e.g., acceleration, rotation, microphone, piezoresistive strain, vibration, position, etc.), electromagnetic (e.g., magnetometers, antenna, cameras, etc.), and chemical or biological (e.g., chemical composition, presence or absence of agents, etc.) data. They are used in a wide variety of applications such as agriculture, weather, aerospace, military, environment or industrial control and monitoring, wildlife monitoring, security monitoring, inventory control, and many others. For example, California Edison's Nuclear Generating Station in San Onofre, Calif. has deployed wireless mesh networked sensors from Dust Networks to obtain real-time trend data. The data are used to predict which motors are about to fail, so they can be preemptively rebuilt or replaced during scheduled maintenance periods. The use of a wireless sensor network therefore saves the station money and avoids potential machine shutdown. Implementation of a sensor localization algorithm would provide a service that eliminates the need to record every sensor's location and its associated ID number in the network.
Wireless sensor networks are potentially important enablers for many other advanced applications. By 2008, there could be 100 million wireless sensors in use, up from about 200,000 in 2005, according to the market-research company Harbor Research. The worldwide market for wireless sensors, it says, will grow from $100 million in 2005 to more than $1 billion by 2009. This is motivating great effort in academia and industry to explore effective ways to build sensor networks with feature-rich services.
In order to make practical use of the data collected by the sensors, the location of each sensor in the network is desired. Accurate locations are typically known for only some of the sensors (which are referred to as anchors) in a wireless sensor network. One approach to localizing sensors with unknown locations is to use known anchor locations and distance measurements that neighboring sensors and anchors obtain among themselves. Sensor locations are estimated using a sparse data matrix of noisy distance measurements. This leads to a large, non-convex, constrained optimization problem. Large networks may contain many thousands of sensors, whose locations are desired to be determined accurately and quickly.
Prior sensor localization methods include use of the satellite-based global positioning system (GPS), triangulation-based multidimensional scaling, convex optimization, and semidefinite programming (SDP) relaxation. Detailed information regarding the prior art methods may be found in the following: J. Hightower and G. Boriello, Location systems for ubiquitous computing, IEEE Computer, 34(8) (2001), pp. 57-66; L. Doherty, L. El Ghaoui, and K. Pister, Convex position estimation in wireless sensor networks, Proc. IEEE Infocom 2001, Anchorage, Ak., April 2001, pp. 1655-1663; and P. Biswas and Y. Ye, Semidefinite programming for ad hoc wireless sensor network localization, IPSN 2004, Berkeley, Calif., Apr. 26-27, 2004.
GPS-based localization suffers from many drawbacks. For example, a GPS-based system is typically very expensive to deploy because the devices using it are more costly. In addition, GPS can be less accurate. Without the use of specialized equipment, normal GPS can pinpoint subject locations with approximately five-meter accuracy. In addition, GPS localization requires line of sight, thus limiting its use to an outdoor environment. Furthermore, for certain applications that require high security, GPS could compromise that requirement through its use of satellite communication. Moreover, due to satellite communication delay, use of GPS might not be an effective method for real-time tracking of moving sensors.
Non-GPS-based methods also suffer from various drawbacks. A significant drawback is that the prior methods are not suitable for large-scale networks. The performance deteriorates rapidly as the network increases in size. The execution times are not fast enough for real-time applications. Another problem is the lack of an indication of the accuracy of each position estimation. Without the knowledge of how accurate the position estimation is, the use of the resulting estimation is very limited. In addition, most triangulation-based methods require the unknown point to be within detecting range of at least three reference points whose locations are already known.
A need therefore exists for a system, method, and software for sensor localization that overcomes the limitations of the prior art. It would be desirable to have non-GPS-based localization algorithms that are effective for the large-scale networks, with minimal localization errors while achieving the efficiency desired for real-time environments.